package twobranchTree.buildTreeTwo;

import java.util.HashMap;
import java.util.Map;

import twobranchTree.preorderTraversal.TreeNode;
/**
 * @Date 2020/02/29
 * @author 王光浩
 * @Thinking 使用递归方式（自己的）
 * @Analysis 时间复杂度：O(n)，空间复杂度O（n）
 */
public class MyMethodOne {
	private Map<Integer,Integer> map=new HashMap<Integer,Integer>(); //用于保存中序遍历结果
	private int[] post;
	private int[] pre;
	public TreeNode buildTree(int[] preorder, int[] inorder) {
		this.post=inorder;
		this.pre=preorder;
		if(preorder.length==0)return null;
		int i=0;
		//将中序遍历结果存入map
		for(int tem:inorder) {
			map.put(inorder[i], i);   //使用值——下标
		}
		TreeNode root=new TreeNode(preorder[0]);
		//进行递归
		recursively(0,preorder.length-1,0,inorder.length-1,root);
		return root;
	}
	/**
	 * 将root的左右子节点进行连接（利用根节点信息，在中序遍历中分出左右子树，然后利用中序遍历的结果，将前序遍历分出左右子树
	 * 最后分别进行遍历）
	 * @param preLeft the index of preorder which is left bound
	 * @param preRight the index of preorder which is right bound
	 * @param inLeft the index of inorder which is left bound
	 * @param inRight the index of inorder which is right bound
	 * @param root the root of the tree
	 */
	private void recursively(int preLeft,int preRight,int inLeft,int inRight,TreeNode root) {
		if(preRight-preLeft==0)return;  //该元素为叶子节点
		int inIndex=map.get(root.val);  //获取根节点在中序遍历中的位置
		//如果左子树为空
		if(inIndex==inLeft) {
			TreeNode tem=new TreeNode(pre[preLeft+1]);
			root.left=null;
			root.right=tem;
			recursively(preLeft+1,preRight,inIndex+1,inRight,tem);
		}
		else if(inIndex==inRight) { //如果右子树为空
			TreeNode tem=new TreeNode(pre[preLeft+1]);
			root.left=tem;
			root.right=null;
			recursively(preLeft+1,preRight,inLeft,inIndex-1,tem);
		}
		//左右子树都不为空
		else {
			int bound=inIndex-inLeft;  //在中序遍历中root节点的左子树节点总个数
			TreeNode left=new TreeNode(pre[preLeft+1]);
			TreeNode right=new TreeNode(pre[preLeft+bound]);
			root.left=left;
			root.right=right;
			//进入左右子树遍历
			recursively(preLeft+1,preLeft+bound-1,inLeft,inIndex-1,left);
			recursively(preLeft+bound,preRight,inIndex+1,inRight,right);
		}
	}
}
